"Andrew Clinton" <ajc### [at] uwaterlooca> wrote:
> What are you planning on researching for your Ph.D? :)

 Still deciding (I've just finished my first 8 months), though I'm 98%
certain it'll be in the area of ray tracing non-static scenes.

> I've now taken a closer look at your code.  I'm guessing that the reason
> you are seeing this difference in performance is that we are using
> different termination criteria for the construction.  When I build the
> tree, I will split even when there is no clean separation.  So if there are two
> objects (A and B) where A straddles the splitting plane but B is on one
> side, I'll still try to subdivide these to separate out a cell that
> contains only B as well as a cell with both.  This would explain the
> larger memory use for the scene you were testing.  I think that my method
> should be more efficient in performance for scenes with overlapping
> objects as long as the memory hit is not too large.  Of course I've just
> hypothesized this after looking at both the sets of code, so I'm not sure.
>  Stopping the subdivision whenever there is no clean separation (like I
> think you are doing) would probably give more stable memory use.

 When I was first developing my kd-tree codebase I was actually encountering
a problem with infinite recursion when trying to split the objects A & B as
you decribe. What was happening is that I was constantly finding the same
splitting plane level after level until I either killed the process or ran
out of memory -- since I don't have a depth bound on my tree. My 'fix' was
to split only when I could find a splitting plane that had at least one
object on either side of the plane (or to split when I could construct a
sensible empty leaf). I can't help but wonder if you're encountering a
similar problem, but that since you have a depth bound it just means that
you're filling out the tree rather than hitting infinite recursion.

 My codebase has changed sufficiently since then, though, that I wonder if I
no longer have that problem... See the use of the emptyLeafs parameter for
Build_KD_Tree and Find_Splitting_Plane -- I should be able to use that
parameter to prevent splits in the same place in consecutive levels.

 I certainly agree that being able to split those types of object sets would
be very beneficial.

> As for overall performance, I've tried rendering a few scenes with both
> patches and found mine to have better performance for most of the standard
> scenes that I've tried.  Unfortunately I don't have enough memory to try
> all the scenes that you've listed but here are some of the results:
>
> A = your patch (-UV -UL +UK)
> B = my patch (+MM2)
>
> rings15:
> A: 16s parse, 71s trace
> B: 11s parse, 81s trace
>
> lattice20:
> A: 10s parse, 33s trace
> B: 9s parse, 43s trace
>
> tree15:
> A: 19s parse, 13s trace
> B: 19s parse, 25s trace
>
> patio-radio:
> A: 0s parse, 100s trace
> B: 0s parse, 96s trace (wrong result?!)
>
> stackertransp:
> A: 8s parse, 27s trace
> B: 8s parse, 22s trace (wrong result?!)

 Had you mixed up A & B for some of these? You mention below that there's an
incorrect result for my version (A) on the last two, but you put the note
beside the timing for your patch (B).

> I received incorrect output from your patch for the last two tests, let me
> know if you can verify or if I've set things up wrong.  The problem could
> be related to the ray flags bug (see my post in povray.unofficial.patches)

 Ack! Thank you for pointing that out. I can't believe that I didn't even
notice that one. It would appear that my patch isn't doing shadows
correctly with the radiosity calculations. Odd, since it does them
correctly on all the SPD scenes... Well, there goes any hope at doing any
real work today... ;)

-Daniel Neilson

Post a reply to this message